import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode.简单题.删除有序数组中的重复项
 */

class Solution {
    //解法一
    public static int removeDuplicates(int[] nums) {
        //i是每个位置最终存放的元素
        int i = 0;
        //j是遍历整个数组的变量
        int j = 1;
        //length作为一个参考，要求i < length
        int length = nums.length;
        //当 length == 1，nums[j]越界
        if(length == 1) {
            return length;
        }
        //前提条件就是 j 只遍历整个数组，i 的大小小于 length 的大小
        while(j < nums.length && i < length) {
            //当nums[i] == nums[j]时，表示存在重复，不存放，并且length减一
            //跳出循环时，要么是 j 遍历了整个数组，要么是遇见不同的元素
            while(j < nums.length && i < length && nums[i] == nums[j] ) {
                j++;
                length--;
            }
            //放新元素的位置应该在之前的 i 的后一个位置，i 需要自增
            i++;
            //当前面不是 j 已经遍历结束的情况时，则一定是出现了新的元素，进行赋值
            if(j < nums.length) {
                nums[i] = nums[j];
            }
            //为了避免下一次 nums[i] 与 nums[j] 进行比较时比较的是 nums[j] 的元素
            //我们需要在赋值结束之后让 j 也自增1
            j++;
        }
        return length;
    }

    //解法一（简化版）
    public static int removeDuplicates1(int[] nums) {
        //i是每个位置最终存放的元素，i 最终的结果 + 1就是数组删除后最终的长度
        int i = 0;
        //j是遍历整个数组的变量
        int j = 1;
        //length就是数组长度
        int length = nums.length;
        //当 length == 1，nums[j]越界
        if(length == 1) {
            return length;
        }
        //前提条件就是 j 只遍历整个数组
        while(j < nums.length) {
            if(nums[i] != nums[j] ) {
                i++;
                nums[i] = nums[j];
            }
            //无论是否赋值，j都需要向后移动一位
            j++;
        }
        return i + 1;
    }

    //解法二
    public static int removeDuplicates2(int[] nums) {
        //i是每个位置最终存放的元素，慢指针，第一个一定有，直接从第二个开始
        //i 最终的结果就是最后数组删除结束后的长度
        int i = 1;
        //j是遍历整个数组的变量，快指针
        int j = 1;
        //length是 nums 数组的长度 , j < nums
        int length = nums.length;
        //当 length == 0时，无元素
        if(length == 0) {
            return length;
        }
        //前提条件就是 j 只遍历整个数组
        while(j < length) {
            //如果有相同的元素，相当于每次存放时只存储第一个
            if(nums[j - 1] != nums[j]) {
                nums[i] = nums[j];
                i++;
            }
            //无论是否存储，j 都要向后走
            j++;
        }
        return i;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,1};
        int length = removeDuplicates(nums);
    }
}

public class Test {
}
